package day_2022_9_to_12.Day;

import java.util.ArrayList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/09/27 22:48
 **/
public class Day26_2_Num131_Partition {
    class Solution {
        List<List<String>> ans = new ArrayList<>();
        public List<List<String>> partition(String s) {
            dfs(s.toCharArray(), 0, new ArrayList());
            return ans;
        }

        void dfs(char[] s, int startIndex, List<String> path) {
            if(startIndex == s.length) {
                ans.add(new ArrayList(path));
                return;
            }
            for(int i = startIndex; i < s.length; i++) {
                if(check(s, startIndex, i)) {
                    path.add(new String(s, startIndex, i - startIndex + 1));
                    dfs(s, i + 1, path);
                    path.remove(path.size() - 1);
                }
            }
        }

        boolean check(char[] s, int start, int end) {
            while(start <= end) {
                if(s[start++] != s[end--]) {
                    return false;
                }
            }
            return true;
        }
    }
}